Scheduling programs facilitate scheduling of tasks that require resources within given time periods. Typically, the scheduling program receives requests for resources needed for the tasks. The scheduling program then attempts to allocate limited resources to tasks that compete for those resources. Based on the allocation, the scheduling program schedules the tasks. For example, a scheduling program may have five conference rooms to assign among five meetings. The meetings may have constraints, such as number of attendees, minimum time duration, etc. Based on the constraints, the scheduling program chooses time slots and resources for the tasks.
Unfortunately, typical task scheduling problems are not as simple as allocating five conference rooms among five meetings. In a hospital setting, for example, there may be many types of medical rooms, staff, equipment, and the like, which can be allocated among hundreds of patients or medical operations, which may require resources in the alternative or in combinations. For example, a medical operation may require either resource “a” or “b” but not both, while another operation may require both resources “c” and “d.” As the size and complexity of task scheduling problems increase, optimal solutions are more difficult to achieve, particularly in an efficient manner.
One task scheduling technique traditionally used is a “brute force” technique. The brute force technique involves representing all possible tasks and their resource requirement alternatives and combinations in a tree structure, and then analyzing every path in the tree to determine which path gives best results. For simple task scheduling problems, the brute force method may work satisfactorily; however, when the problem becomes complex, the tree structure becomes correspondingly complex, with countless alternative paths to be analyzed. The analysis of every path in such a complex tree structure can become NP (nondeterministic polynomial time) hard; i.e., computationally impractical. As a result, solving a complex task scheduling problem using brute force methods can be extremely inefficient and/or unworkable.
Other task scheduling algorithms apply heuristics that are not well founded. These algorithms often employ task scheduling rules that are not based on scientific or logical reasoning, but rather intuitive notions. One heuristic technique employs “greedy” heuristics in which the solution is constructed sequentially without regard for the effect that a resource allocation choice might have upon other requested tasks. Greedy algorithms are attractive due to their simplicity. While a greedy technique may yield optimal results sometimes, it can yield extremely sub-optimal results. As with other heuristic techniques, the success, or lack of success, of a greedy technique is typically haphazard.